#pragma once

#include <tuple>
#include <vector>

namespace solution_098
{

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution
{
public:
    bool isValidBST(TreeNode* root)
    {
        if (root == nullptr)
            return true;
        return std::get<0>(traverse(root));
    }

    std::tuple<bool, int, int> traverse(TreeNode* root)
    {
        std::tuple<bool, int, int> ret { false, root->val, root->val };

        if (root->left) {
            if (root->left->val < root->val) {
                auto [ok, left_min, left_max] = traverse(root->left);
                if (ok && left_max < root->val) {
                    std::get<0>(ret) = true;
                    std::get<1>(ret) = left_min;
                }
            }
        } else {
            std::get<0>(ret) = true;
        }

        if (!std::get<0>(ret))
            return ret;
        std::get<0>(ret) = false;

        if (root->right) {
            if (root->right->val > root->val) {
                auto [ok, right_min, right_max] = traverse(root->right);
                if (ok && right_min > root->val) {
                    std::get<0>(ret) = true;
                    std::get<2>(ret) = right_max;
                }
            }
        } else {
            std::get<0>(ret) = true;
        }

        return ret;
    }
};

}  /* namespace solution_098 */
